package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
 */
public class _700_二叉搜索树中的搜索 {
    /**
     * 迭代 层序遍历
     * @param root 根节点
     * @param val 目标值
     * @return TreeNode
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }

        while (root != null) {
            if (root.val == val) {
                return root;
            }
            root = val < root.val ? root.left : root.right;
        }
        return root;
    }

    /**
     * 递归 前序遍历
     * @param root 根节点
     * @param val 目标值
     * @return TreeNode
     */
    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }

        return searchBST(val < root.val ? root.left : root.right, val);
    }
}
